import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

/**
 *  算法实验二
 *  分治算法
 */
public class FindBadCoin {
    public  static int CountWeight(int[] coins,int left,int right) {
        int i = 0;
        int sum = 0;
        for(i=left;i<=right;i++) {
            sum += coins[i];
        }
        return sum;
    }

    public static int FindBadCoin(int[] coins, int left, int right) {
        //N个硬币
        int N = right-left+1;
        //当硬币剩余2个的时候结束
        if(N == 2) {
            if(coins[left] > coins[right]) {
                return left;

            }else {
                return right;
            }
        }
        //平均大小
        int AvgSize = N / 3;
        //将N个硬币分为三组
        int FirstGroupEnd = left + AvgSize - 1;
        int SecondGroupEnd = left + 2 * AvgSize - 1;
        //计算前两组硬币的大小
        int ret1 = CountWeight(coins,left,FirstGroupEnd);
        int ret2 = CountWeight(coins,FirstGroupEnd+1,SecondGroupEnd);
        //三种情况
        if(ret1 == ret2) {
           return FindBadCoin(coins,SecondGroupEnd+1,right);
        }else if(ret1 > ret2) {
           return FindBadCoin(coins,left,FirstGroupEnd);
        }else {
           return FindBadCoin(coins,FirstGroupEnd+1,SecondGroupEnd);
        }
    }

    public static void main(String[] args) {
        // N个硬币，里面有一个超重的银币
        int N = 8;
        int[]coins = new int[N];
        // 将合格的硬币设为1
        for(int i = 0;i < N;i++) {
            coins[i]=1;
        }
        // 将第3个硬币设为超重，即下标为2的
        coins[7] = 2;
        //打印原始数据
        System.out.println("原数据为:" + Arrays.toString(coins));
        //找到超重硬币的下标
        int ret = FindBadCoin(coins,0,coins.length-1);
        System.out.println("超重硬币的下标为:" + ret);
    }
}
